/**
 * 135. 分发糖果
 * https://leetcode.cn/problems/candy/
 * 老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
 *
 * 你需要按照以下要求，帮助老师给这些孩子分发糖果：
 *
 * 每个孩子至少分配到 1 个糖果。
 * 相邻的孩子中，评分高的孩子必须获得更多的糖果。
 * 那么这样下来，老师至少需要准备多少颗糖果呢？
 *
 * 示例 1:
 *
 * 输入: [1,0,2]
 * 输出: 5
 * 解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
 * 示例 2:
 *
 * 输入: [1,2,2]
 * 输出: 4
 * 解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果，这已满足上述两个条件。
 */
public class Q9_p135_H {
    /**
     * 总的思路局部最小值为1，局部最小值左右两侧依次增加1
     * 但是这样思考实现十分复杂，因为局部最大值不仅要考虑左侧还要考虑右侧
     * 因此使用两次遍历，一次只考虑右侧，一次只考虑左侧
     * 第一次遍历，从前往后遍历。当前评分大于前一个评分，那么当前获取的糖果比前一个多一个
     * 当前评分小于等于前一个评分，则获取糖果为1，此时只是临时值，会在在下一次遍历修改
     * 第一个人糖果初始化为1
     * 第二次遍历，从后往前遍历，如果当前评分大于后一个评分，那么当前获取的糖果比前一个多一个（且不小于上一次的赋值）
     * 如果当前评分小于等于后一个评分，不需要修改
     */
    static class Solution {
        public int candy(int[] ratings) {
            int n = ratings.length;
            int[] candyVec = new int[n];
            candyVec[0]=1;
            for (int i = 1; i < n; i++) {
                if(ratings[i]>ratings[i-1]) {
                    candyVec[i] = candyVec[i-1]+1;
                }else{
                    candyVec[i] = 1;
                }
            }
            for (int i = n-2; i >=0 ; i--) {
                if(ratings[i]>ratings[i+1]) {
                    candyVec[i] = Math.max(candyVec[i],candyVec[i+1]+1);
                }
            }
            int sum = 0;
            for (int i : candyVec) {
                sum+=i;
            }
            return sum;
        }
    }
}
